iT邦幫忙

2019 iT 邦幫忙鐵人賽
DAY 28
0
自我挑戰組

大四資工人生，快畢業了，然後呢系列 第 28 篇

#資工人生─Day28─演算法

2019鐵人賽
2491 瀏覽

  • 分享至 

  • xImage
    •  

前言

今天來寫寫演算法的理論

  • Knapsack Problem
    • problem statment
      • fractional KP
        • 輸入: n個item (第i個重Wi值vi)及W(最大負重)
        • 輸出: 最大profit(獲利)
        • 限制:
          1. 取物總重<= W
          2. 取物時可只取物品的部分(有一個item重3kg,可只取其中2kg)
      • 0/1KP
        • 同上，但取物時得全取
    • fractional KP
      • 解法:greedy
        • 從目前 vi/wi(單位價值)最高物品開始取until 物品拿完or 負重=W
        • algo:
          • Time complexity
        • ex
          • W = 5
item vi wi
1 10 2
2 6 1
3 12 3

上一篇
#資工人生─Day27─資料庫
下一篇
#資工人生─Day29─演算法DP
系列文
大四資工人生，快畢業了，然後呢 共 31 篇
  1. 27
    #資工人生─Day27─資料庫
  2. 28
    #資工人生─Day28─演算法
  3. 29
    #資工人生─Day29─演算法DP
  4. 30
    #資工人生─Day30─網頁設計那件事情
  5. 31
    #資工人生─資工人生做個整理XD
完整目錄
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
547 組
團體組數
24 組
累計文章數
6144 篇
最後報名日
9/15
iT+看影片追技術 看影片追技術 看更多
熱門tag
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 17th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 18th鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# linux windows server css
熱門問題
熱門回答
熱門文章
IT邦幫忙